Куркчи Вячеслав Андреевич
kourktchi@ukrtop.com
магистрант группы ПО-99, ФВТИ
научный руководитель:
Ладыженский Юрий Валентинович

тема магистерской работы:
Параллельные алгоритмы для решения задач на графах.

• Ладыженский Ю.В., Куркчи В.А. Параллельные алгоритмы поиска независимых множеств на графах.//Материалы второй конференции "Донбасс-2020".-2004, стр.609-616.   [pdf] (215 кб)
       В статье приведены два паралельных эвристических алгоритма для поиска наибольшего независимого множества. Модифицирован алгоритм Голдберга-Спенсера. Рассмотрен алгоритм, основанный на базе жадной эвристики и ограниченного перебора. Приведены результати тестирования обоих алгоритмов, сделаны выводы по поводу их точности.
  

• Куркчи В.А. Исследование алгоритмов поиска максимальных независимых множеств на графах. Студенческая научная работа (поошрительный диплом всеукраинского конкурса НИРС 2002г.)   [pdf] (329 кб)
       В данной работе представлены результаты исследования алгоритмов для нахождения максимальных независимых множеств вершин. Был рассмотрен алгоритм Брона-Кэрбоша, и произведена его модификация.
       Для проверки эффективности работы алгоритмов была разработана программа на языке Visual C++ 6.0, проведен ряд экспериментов и сделаны заключения относительно эффективности модификаций алгоритма по сравнению с оригиналом: показано, что полученные алгоритмы затрачивают на решение меньше времени.
  

• Голдберг М., Спенсер Т. Параллельное построение наибольшего независимого множества. Перевод с английского Куркчи В.А. [pdf] (208 кб)
       Рассмотрена задача параллельного построения наибольшего независимого множества данного графа. Представлен новый детерминированный NC-алгоритм для модели EREW PRAM. Для графов с n вершинами и m ребрами он использует O((n+m)/lgn) процессоров и завершает работы за время O(log³n), уменьшая в logn раз и время, и количество используемых процессоров, по сравнению с предыдущими детерминированными алгоритмами, решающими задачу, используя линейное количество процессоров.
  

• Goldberg M., Spenser T. Новый параллельный алгоритм для задачи о наибольшем независимом множесте [pdf - по-английски] (189 кб)
       Взято с www.cs.rpi.edu/~goldberg/publications/papers-reversed.html
       Построен новый алгоритм для решения задачи о наибольшем независимом множестве. Он выполняется за время O(log⁴N) при реализации на линейном числе EREW процессоров. Это первый детерминированный алгоритм, который выполняется за полилогарифмическое время и выработка процессорного времени которого оптимизирована до полилогарифмического множителя.
  

• Bomze M., Budinich M., Pardalos P.M., Pelillo M. The maximum clique problem. in: Handbook of combinatorial optimization. – Adison-Wesley Publishing Company: 1998, 2410pp.[pdf - по-английски] (535 кб)
       Взято с www.dsi.unive.it/~pelillo/papers/chapter-clique.ps.gz
       Задача о наибольшей клике - классическая задача комбинаторной оптимизации для которой нашли важные применения в различных областях. В этой статье мы пытаемся привести обзор результатов касающихся алгоритмов, сложности, и приложений этой задачи, и также приводим дополненную библиографию. Конечно, мы основываемся на предшествующих работах о подобных задачах.